#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NAME_LENGTH 100

// 顺序串类型
typedef struct {
	char data[MAX_NAME_LENGTH];
	int length;
} SqString;

// 二叉树节点
typedef struct BTNode {
	SqString Husband;   // 丈夫姓名
	SqString Wife;      // 妻子姓名
	struct BTNode *lchild; // 左孩子（第一个孩子）
	struct BTNode *rchild; // 右孩子（第二个孩子）
} BTNode;

// 创建节点
BTNode* createNode(SqString husband, SqString wife) {
	BTNode *node = (BTNode *)malloc(sizeof(BTNode));
	node->Husband = husband;
	node->Wife = wife;
	node->lchild = NULL;
	node->rchild = NULL;
	return node;
}
// 函数原型
void findChildren(BTNode* root, SqString parentName, SqString* children, int* count);
void findAncestors(BTNode* root, SqString name, SqString* ancestors, int* count);
void findSiblings(BTNode* root, SqString name, SqString* siblings, int* count);
void addChild(BTNode* root, SqString parentName, SqString childName);
void addSpouse(BTNode* root, SqString name, SqString spouseName);

// 查找孩子
void findChildren(BTNode* root, SqString parentName, SqString* children, int* count) {
	if (root == NULL) return;
	
	if (strcmp(root->Husband.data, parentName.data) == 0 || strcmp(root->Wife.data, parentName.data) == 0) {
		if (root->lchild != NULL) {
			children[(*count)++] = root->lchild->Husband; // 假设第一个孩子是丈夫
		}
		if (root->rchild != NULL) {
			children[(*count)++] = root->rchild->Husband; // 假设第二个孩子是丈夫
		}
	} else {
		findChildren(root->lchild, parentName, children, count);
		findChildren(root->rchild, parentName, children, count);
	}
}

// 查找祖先
void findAncestors(BTNode* root, SqString name, SqString* ancestors, int* count) {
	if (root == NULL) return;
	
	if (strcmp(root->Husband.data, name.data) == 0 || strcmp(root->Wife.data, name.data) == 0) {
		// 找到父母
		if (root->lchild != NULL) {
			ancestors[(*count)++] = root->Husband; // 添加丈夫
		}
		if (root->rchild != NULL) {
			ancestors[(*count)++] = root->Wife; // 添加妻子
		}
		return;
	}
	
	findAncestors(root->lchild, name, ancestors, count);
	findAncestors(root->rchild, name, ancestors, count);
}

// 查找兄弟姐妹
void findSiblings(BTNode* root, SqString name, SqString* siblings, int* count) {
	if (root == NULL) return;
	
	// 假设兄弟姐妹在同一父母下
	if (strcmp(root->Husband.data, name.data) == 0 || strcmp(root->Wife.data, name.data) == 0) {
		if (root->lchild != NULL && strcmp(root->lchild->Husband.data, name.data) != 0) {
			siblings[(*count)++] = root->lchild->Husband; // 添加兄弟姐妹
		}
		if (root->rchild != NULL && strcmp(root->rchild->Husband.data, name.data) != 0) {
			siblings[(*count)++] = root->rchild->Husband; // 添加兄弟姐妹
		}
	} else {
		findSiblings(root->lchild, name, siblings, count);
		findSiblings(root->rchild, name, siblings, count);
	}
}

// 添加孩子
void addChild(BTNode* root, SqString parentName, SqString childName) {
	if (root == NULL) return;
	
	if (strcmp(root->Husband.data, parentName.data) == 0 || strcmp(root->Wife.data, parentName.data) == 0) {
		if (root->lchild == NULL) {
			// 添加为左孩子
			SqString child;
			strcpy(child.data, childName.data);
			child.length = strlen(child.data);
			root->lchild = createNode(child, (SqString){"", 0});
		} else if (root->rchild == NULL) {
			// 添加为右孩子
			SqString child;
			strcpy(child.data, childName.data);
			child.length = strlen(child.data);
			root->rchild = createNode(child, (SqString){"", 0});
		} else {
			printf("该家庭已满，无法添加更多孩子。\n");
		}
	} else {
		addChild(root->lchild, parentName, childName);
		addChild(root->rchild, parentName, childName);
	}
}

// 添加配偶
void addSpouse(BTNode* root, SqString name, SqString spouseName) {
	if (root == NULL) return;
	
	if (strcmp(root->Husband.data, name.data) == 0) {
		strcpy(root->Wife.data, spouseName.data);
		root->Wife.length = strlen(spouseName.data);
	} else if (strcmp(root->Wife.data, name.data) == 0) {
		strcpy(root->Husband.data, spouseName.data);
		root->Husband.length = strlen(spouseName.data);
	} else {
		addSpouse(root->lchild, name, spouseName);
		addSpouse(root->rchild, name, spouseName);
	}
}
void DispStr(SqString s)	//输出串s
{
	int i;
	if (s.length>0)
	{	for (i=0;i<s.length;i++)
		printf("%c",s.data[i]);
		printf("\n");
	}
}
void DispBTree(BTNode *b) 
{
	if (b!=NULL)
	{	
		printf("[");
		printf("丈夫：");
		DispStr(b->Husband);
		if(b->Wife.data[0]!='\0')
		{
			printf("妻子：");
			DispStr(b->Wife);
		}
		printf("]");
		if (b->lchild!=NULL || b->rchild!=NULL)
		{	printf("(");						//有孩子节点时才输出(
			DispBTree(b->lchild);				//递归处理左子树
			if (b->rchild!=NULL) printf(",");	//有右孩子节点时才输出,
			DispBTree(b->rchild);				//递归处理右子树
			printf(")");						//有孩子节点时才输出)
		}
	}
}
// 示例程序
int main() {
	
	SqString husband = {"苏序", 6};
	SqString wife = {"史氏", 6};
	BTNode* root = createNode(husband, wife);
	
	// 添加孩子
	addChild(root, husband, (SqString){"苏涣", 6});
	addChild(root, husband, (SqString){"苏洵", 6});

	
	
	
	
	
	// 查找孩子
	SqString ancestors[10];
	int count = 0;
	findAncestors(root, husband, ancestors, &count);
	
	printf("孩子们: ");
	for (int i = 0; i < count; i++) {
		printf("%s ", ancestors[i].data);
	}
//	DispBTree(root);
	printf("\n");
	
	return 0;
}


//编写一个程序，采用一个二叉树表示一个家谱关系（由若干个家谱记录构成，每个家谱记录由丈夫、妻子的姓名组成），每家最多两个孩子，程序具有以下功能。家庭成员中姓名采用第四章的顺序串SqString类型。
//
//(1) 查找某人(参数为父亲姓名或者母亲姓名)的孩子们。
//
//(2) 查找某人的所有祖先，如苏轼的祖先：祖父母苏序和史氏，伯父母苏涣和杨氏，父母苏洵和程氏。
//
//(3) 查找某人同代的所有兄弟姐妹，如跟苏辙同一代的兄弟姐们包括：堂兄弟苏不欺和苏不疑，兄弟苏轼。
//
//(4) 给某人添加孩子。
//
//(5) 某单身人士结婚后添加妻子姓名。
//
//(4)(5)实现的时候，从根节点开始寻找这个人
//(6) 设置一个初始化函数，可以直接建立一个家谱二叉树
